class Node:
    def __init__(self, x=0):
        self.value = x
        self.left = None
        self.right = None
        self.parent = None


def find_sucessor_node(node: Node):
    """
    一棵树的节点还存在一个指向父节点的指针，快速找某个节点的后继节点，后继节点为中序遍历后的下一个节点
    方法一：记录树的中序遍历结果，在表中找到后继节点
    方法二:(1) 若该节点存在右子树，则后继节点为右子树的最左节点
           (2) 若该节点不存在右子树，判断其是否是其父节点的左孩子
           返回空表示该节点为最右节点
    :param node:
    :return:
    """
    if node.right:
        node = node.right
        while node.left:
            node = node.left
        return node
    else:
        while node.parent and node != node.parent.left:
            node = node.parent

        return node.parent


if __name__ == "__main__":
    head = Node(6)
    head.parent = None
    head.left = Node(3)
    head.left.parent = head
    head.left.left = Node(1)
    head.left.left.parent = head.left
    head.left.left.right = Node(2)
    head.left.left.right.parent = head.left.left
    head.left.right = Node(4)
    head.left.right.parent = head.left
    head.left.right.right = Node(5)
    head.left.right.right.parent = head.left.right
    head.right = Node(9)
    head.right.parent = head
    head.right.left = Node(8)
    head.right.left.parent = head.right
    head.right.left.left = Node(7)
    head.right.left.left.parent = head.right.left
    head.right.right = Node(10)
    head.right.right.parent = head.right

    test = head.left.left
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.left.left.right
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.left
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.left.right
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.left.right.right
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.right.left.left
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.right.left
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.right
    print(test.value, "next: ", find_sucessor_node(test).value)
    test = head.right.right
    print(test.value, "next: ", find_sucessor_node(test))
